package org.example.hansp.array_.arraydemo;

import java.util.Arrays;
import java.util.Scanner;

public class ArrayAddAndSort {
    public static void main(String[] args) {
        int[] arr={10,12,45,90};
        Scanner sc=new Scanner(System.in);
        System.out.println("Enter a number:");
        int n=sc.nextInt();

        // 打印插入前的数组
        System.out.println("插入前的数组: " + Arrays.toString(arr));

        int [] newArr=insertIntoSortedArray(n,arr);
        // 打印插入后的数组
        System.out.println("插入后的数组: " + Arrays.toString(newArr));
    }

    /**
     *  在升序数组中插入一个新元素，并保持数组的升序
     * @param n     需要插入的数据
     * @param arr   插入前数组
     * @return      插入后数组
     */
   public static int[] insertIntoSortedArray(int n, int[] arr) {

        System.out.println("插入位置：");
        int index=SearchInsertPosition(arr,n);
        /* int index = binarySearchInsertPosition(arr, n);*/

        System.out.println(index);
        int[] newArr=new int[arr.length+1];
       /* for (int i=0;i<newArr.length;i++){
            if(i<index){
                newArr[i]= arr[i];
            }else if(i==index){
                newArr[i]=n;
            }else{
                newArr[i]= arr[i-1];
            }
        }*/
       for(int i=0,j=0;i<newArr.length;i++){
           if(i!=index){
               newArr[i]=arr[j];
               j++;
           }else{
               newArr[i]=n;
           }
       }

        return newArr;
    }

    /**
     * 使用遍历查找插入位置
     * @param arr  已排序的数组
     * @param n    要插入的数据
     * @return      插入位置的索引
     */
   public static int SearchInsertPosition(int[] arr, int n) {
       int index=-1;
        for (int i = 0; i< arr.length; i++){
            if (arr[i]> n){
                index =i;
                break;
            }
        }
        if (index == -1) {
            index = arr.length;
        }
        return index;
    }

    /**
 * 使用二分查找找到插入位置。
 *
 * @param arr        已排序的数组
 * @param newElement 要插入的元素
 * @return 插入位置的索引
 */
public static int binarySearchInsertPosition(int[] arr, int newElement){
    int left=0;
    int right=arr.length-1;
    while (left<=right){
        int mid=(left+right)/2;
        if (arr[mid]==newElement){
            return mid;
        }
        if (arr[mid]>newElement){
            right=mid-1;
        }
        else if (arr[mid]<newElement){
            left=mid+1;
        }
    }
    return left;//插入位置是左边界
}
}
